두음 법칙 끝말잇기

승패 전파와 가지치기

'두음 법칙 끝말잇기'를 위한 이분 유향 그래프 모델에서도, 우리는 '승패 전파와 가지치기'라는 핵심 원리를 적용하여 게임의 승패를 분석할 수 있습니다.

하지만 가장 중요한 차이점은, 이제 승패 여부가 '음절'이 아닌 '역할이 부여된 정점'에 귀속된다는 점입니다. 즉, '끝 음절'과 '첫 음절'은 그래프상에서 완전히 다른 정점이므로, 이들의 필승/필패 여부도 독립적으로 결정됩니다. 예를 들어, '끝 음절' 례는 '예'로 변신할 수 있는 강력한 선택지 덕분에 필승일 수 있지만, '첫 음절' 례는 사용할 단어가 마땅치 않아 필패일 수도 있습니다.

이분 그래프에서의 승패 전파 알고리즘

알고리즘의 기본 골격은 표준 모델과 유사합니다. 승패가 결정된 정점들을 스택(Stack)이나 큐(Queue)에 넣어 관리하며, 더 이상 새로운 정점의 승패를 결정할 수 없을 때까지 전파와 가지치기를 반복합니다.

시작점: '막다른 길' 찾기

가장 먼저, 양쪽 집합에서 나가는 엣지가 전혀 없는 '막다른 길' 정점을 찾습니다.

'첫 음절' 막다른 길: 이 음절로 시작하는 단어가 사전에 하나도 없는 경우.
'끝 음절' 막다른 길: 이 음절에 적용할 수 있는 두음 법칙 변환이 아예 없는 경우.

이러한 막다른 길 정점들은 모두 필패(Losing)로 확정하고 스택에 추가합니다.

네 가지 핵심 전파 규칙

스택에서 정점을 하나씩 꺼내어, 그 정점의 종류(끝/첫 음절)와 상태(필승/필패)에 따라 다음 4가지 규칙을 적용하여 새로운 승패를 결정하고 스택에 추가합니다.

규칙 1: (끝 음절, 필패) → (첫 음절, 필승)

상황: 필패가 확정된 '끝 음절' $v_{last}$ 를 스택에서 꺼냄.
논리: $v_{last}$ 로 이어지는 '첫 음절' $v_{first}$ 에서는, $v_{last}$ 로 끝나는 단어를 말함으로써 상대를 확실한 필패 포지션에 빠뜨릴 수 있습니다. 이는 명백한 '이기는 수'입니다.
결정: 따라서 $v_{first}$ 는 필승(Winning)으로 확정됩니다.

규칙 2: (첫 음절, 필승) → (끝 음절, 필승)

상황: 필승이 확정된 '첫 음절' $v_{first}$ 를 스택에서 꺼냄.
논리: $v_{first}$ 로 이어지는 '끝 음절' $v_{last}$ 에서는, 두음 법칙을 적용하여 필승 포지션인 $v_{first}$ 로 이동하는 선택지가 존재합니다. 이길 수 있는 선택지가 하나라도 있다면 그 포지션은 필승입니다.
결정: 따라서 $v_{last}$ 는 필승(Winning)으로 확정됩니다.

규칙 3: (끝 음절, 필승) → (첫 음절, 필패)

상황: 필승이 확정된 '끝 음절' $v_{last}$ 를 스택에서 꺼냄.
논리: 이 $v_{last}$ 로 이어지는 '첫 음절' $v_{first}$ 의 입장에서, 만약 $v_{first}$ 에서 나가는 모든 단어 엣지가 이미 '필승'으로 확정된 '끝 음절'들로만 이어진다면, 어떤 단어를 말해도 상대를 필승 포지션으로 만들어주게 됩니다.
결정: 이 경우에만 $v_{first}$ 는 필패(Losing)로 확정됩니다. (다른 선택지가 있다면 판별 보류)

규칙 4: (첫 음절, 필패) → (끝 음절, 필패)

상황: 필패가 확정된 '첫 음절' $v_{first}$ 를 스택에서 꺼냄.
논리: 이 $v_{first}$ 로 이어지는 '끝 음절' $v_{last}$ 의 입장에서, 만약 $v_{last}$ 에서 두음 법칙을 적용할 수 있는 모든 경우의 수가 이미 '필패'로 확정된 '첫 음절'들뿐이라면, 어떤 선택을 해도 필패 포지션으로 갈 수밖에 없습니다.
결정: 이 경우에만 $v_{last}$ 는 필패(Losing)로 확정됩니다. (다른 선택지가 있다면 판별 보류)

이분 그래프에서의 루프 분석

이분 그래프에서는 정점이 항상 다른 집합으로만 연결되므로, $a→a$ 형태의 직접적인 루프는 존재할 수 없습니다. 대신, 두 정점 사이를 왕복하는 2-사이클이 루프의 역할을 합니다.

이분 그래프 루프의 정의: '첫 음절' $a$ 에서 '끝 음절' $b$ 로 가는 단어 엣지가 존재하고, 동시에 '끝 음절' $b$ 에서 '첫 음절' $a$ 로 가는 두음 법칙 엣지가 존재하는 경우, 이 $(a,b)$ 쌍을 루프 구조로 봅니다.

이러한 루프 구조만을 유일한 선택지로 갖는 정점의 승패는 루프의 개수에 따라 결정됩니다.

루프 규칙: '첫 음절' $a$ 에서 나갈 수 있는 모든 단어가 각각 루프 구조를 형성하고 다른 선택지는 없을 때, 그 루프의 총 개수 $n$ 이 홀수이면 $a$ 는 필승, 짝수이면 필패이다.

이 루프 규칙을 '막다른 길 찾기' 단계에 추가함으로써, 우리는 두음 법칙 끝말잇기에 대한 승패 전파 알고리즘을 완성할 수 있습니다.